package com.leetcode;

public class Leetcode152 {
    //思考：DP如何演进：1）状态如何定义？ 2）状态如何转移？

    //容易犯错1：一个数也能当做最后的结果
    //容易放错2：负负得正，不能遇到负数就把当前的值给抛弃了。
    //正确的理解是：记录每一个max，和min，
    // 即：max = Math.max(max[i-1]*ai,min[i-i]*ai,ai)
    //min = Math.min(max[i-1]*ai,min[i-i]*ai,ai)
    public int maxProduct(int[] nums) {
        int length = nums.length;
        //保存max[i-1]*ai最大值
        int[] maxF = new int[length];
        //保存min[i-1]*ai最小值
        int[] minF = new int[length];
        System.arraycopy(nums, 0, maxF, 0, length);
        System.arraycopy(nums, 0, minF, 0, length);
        for (int i = 1; i < length; ++i) {
            //nums[i]是可能成为最大值的，如[0,2]
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
        }
        int ans = maxF[0];
        for (int i = 1; i < length; ++i) {
            ans = Math.max(ans, maxF[i]);
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        Leetcode152 leetcode152 = new Leetcode152();
        System.out.println(leetcode152.maxProduct(nums));
    }
}
